package com.zwj.interview.排序;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入一个区间的集合，请将重叠的区间合并。每个区间用两个数字比较，
 * 分别表示区间的起始位置和结束位置。例如，输入区间[[1，3]，[4，5]，[8，10]，[2，6]，[9，12]，[15，18]]，
 * 合并重叠的区间之后得到[[1，6]，[8，12]，[15，18]]
 */
public class 合并区间 {

    /**
     * @param intervals
     * @return
     * 函数Arrays.sort对输入的区间数组进行排序。排序的标准由lambda表达式“（i1，i2）->i1[0]-i2[0]”确定，
     * 该lambda表达式表明将两个区间i1和i2的起始位置（i1[0]和i2[0]）进行比较，并将起始位置小的排在前面
     */
    public int[][] merge(int[][] intervals) {
        //针对每个区间，按照每个区间的第一个数字进行排序
        Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]);
        List<int[]> merged = new LinkedList<>();
        int i = 0;
        while (i < intervals.length) {
            //拿到每一个区间的两个数字
            int[] temp = new int[]{intervals[i][0], intervals[i][1]};
            int j = i + 1;
            //如果说当前区间的后一个数字大于下一个区间的第一个数字，那么就可以合并这两个区间
            while (j < intervals.length && intervals[j][0] <= temp[1]) {
                //将当前区间的第二个数字更新为第二个区间的第二个数字
                temp[1] = Math.max(temp[1], intervals[j][1]);
                //推进下一个区间的值
                j++;
            }
            merged.add(temp);
            //更新i的值
            i = j;
        }
        int[][] result = new int[merged.size()][];
        return merged.toArray(result);
    }


}
